#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <time.h>



#include <iostream>
#include <fstream>
#include <vector>
#include <list>
#include <algorithm>

#include "NuclSeq.h"

#include "nickers.h"

#ifndef VAR
#define VAR(i,v) __typeof((v))i=(v)
#define FOREACH(i,v) for(VAR(i,(v).begin());i!=(v).end();i++)
#endif

/*
 * main.cpp
 *
 *  Created on: 2009-03-28
 *      Author: chriss
 */

using namespace std;

const int MAX_ITERS = 100;

class NuclPair
{
public:
	int el;
	int pos;

	NuclPair(int e, int p)
	{
		this->el = e;
		this->pos = p;
	}

	~NuclPair()
	{
	}

};

/* load data*/
void loadData(char * fileName, int size, vector<char*>& v)
{

	char * buf;
	char temp[20];
	FILE *f = fopen(fileName, "r");

	while (fgets(temp, size, f))
	{
		for(int i=0; i<20 && temp[i]!=0; i++)
			if (! ((temp[i]>='a' && temp[i]<='z')
				|| (temp[i]>='A' && temp[i]<='Z')) )
			{
				temp[i] = '\0';
			}
		buf = new char[20];
		strcpy(buf, temp);
		buf[10] = 0x0;
		v.push_back(buf);
	}
	fclose(f);
}

void cleanUp(vector<char*>& vec, int **graph)
{
	for (unsigned int i = 0; i < vec.size(); ++i)
		delete[] graph[i];
	delete[] graph;

	for (unsigned i = 0; i < vec.size(); ++i)
		delete[] vec[i];

	vec.clear();
}

int compNucl(const char * nuclA, const char * nuclB)
{

	int offset = 0;
	int i = 0;
	for (offset = 0; offset < 10; ++offset)
	{
		for (i = 0; i < 10 - offset; ++i)
			if (nuclA[i + offset] == nuclB[i])
				continue;
			else
				break;

		if (i == (10 - offset))
			break;
	}
	return offset;
}

void createGraph(vector<char*>& vec, int **graph)
{

	int i, j;
	int n = vec.size();

	//printf("%d\n", vec.size());

	for (i = 0; i < n; ++i)
		for (j = 0; j < n; j++)
			graph[i][j] = compNucl(vec[i], vec[j]);

	return;
}

/* complexity O(n^2) */

void greedyTSP(int **graph, NuclSeq& base, int start, int size, int maxPath)
{

	int i, cur, minFront, minBack;

	vector<int> pre;
	vector<int> succ;
	vector<int> ptr;
	int len = 10;
	int nuclLeft = size;
	char *visited;
	visited = new char[size];
	memset(visited, 'n', size);

	base.clear();
	visited[start] = 'v';
	base.seq.push_back(start);
	base.end = 1;

	while (len < maxPath)
	{
		minFront = minBack = 1000;
		pre.clear();
		succ.clear();
		for (i = 0; i < size; ++i)
		{
			if (visited[i] == 'v')
				continue;

			if (graph[i][base.seq[0]] == minBack)
				pre.push_back(i);
			else
				if (graph[i][base.seq[0]] < minBack)
				{
					minBack = graph[i][base.seq[0]];
					pre.clear();
					pre.push_back(i);
				}

			if (graph[base.seq[base.seq.size() - 1]][i] == minFront)
				succ.push_back(i);
			else
				if (graph[base.seq[base.seq.size() - 1]][i] < minFront)
				{
					minFront = graph[base.seq[base.seq.size() - 1]][i];
					succ.clear();
					succ.push_back(i);
				}
		}//end for
		if ((pre.size() == 0) && (succ.size() == 0))
			break;
		if (maxPath - len < (minBack < minFront ? minBack : minFront))
			break;

		//printf("f %d b %d\n", minFront, minBack);
		if (minBack < minFront)
		{
			//printf("%d %d = %d\n",len,minBack,maxPath);
			if ((len + minBack) > maxPath)
				break;
			cur = pre[rand() % pre.size()];
			base.seq.insert(base.seq.begin(), cur);
			len += minBack;
			visited[cur] = 'v';
			++base.end;
			--nuclLeft;
		}
		else
		{
			if ((len + minFront) > maxPath)
				break;
			cur = succ[rand() % succ.size()];
			base.seq.push_back(cur);
			len += minFront;
			visited[cur] = 'v';
			++base.end;
			--nuclLeft;
		}

	}

	// dopisywanie reszty na koniec
	/*minFront = 10000;
	cur = 0;
	while (--nuclLeft)
	{
		for (i = 0; i < size; ++i)
		{
			if (visited[i] == 'v')
				continue;

			if (graph[base.seq[base.seq.size() - 1]][i] < minFront)
			{
				minFront = graph[base.seq[base.seq.size() - 1]][i];
				cur = i;
			}

		}
		visited[cur] = 'v';
		base.seq.push_back(cur);

	}*/

	delete[] visited;

}

double evalEnergy(NuclSeq& baseSeq, int **distGraph, int size)
{
	int len = 10;
	int i = 0;
	baseSeq.end = 1;
	while (1)
	{
		if ((len + distGraph[baseSeq.seq[i]][baseSeq.seq[i + 1]]) > size)
			break;
		len += distGraph[baseSeq.seq[i]][baseSeq.seq[i + 1]];

		++(baseSeq.end);
		++i;
	}

	return (double) 1000 - baseSeq.end;
}

void generateNeighbour(const NuclSeq& baseSeq, int **distGraph, NuclSeq& newSeq)
{

	newSeq.clear();

	newSeq.seq.insert(newSeq.seq.begin(), baseSeq.seq.begin(),
			baseSeq.seq.end());
	newSeq.end = baseSeq.end;

	/*
	 if (newSeq.seq.size()==newSeq.end)
	 return;
	 int tmp = newSeq.end + rand()%(newSeq.seq.size()-newSeq.end);
	 int pos = tmp;

	 vector<int>::iterator it = newSeq.seq.begin();
	 vector<int>::iterator it2 = newSeq.seq.begin();

	 while(--tmp)
	 ++it;

	 int tmp2 = 1+ rand()%(newSeq.end-1);

	 while(--tmp2)
	 ++it2;
	 newSeq.seq.insert(it2, pos);
	 newSeq.seq.erase(it);
	 */

}

void TSinsert(int **graph, list<int>& main, list<int>& rest, int& curPath)
{

	list<int>::iterator mainIt1;
	list<int>::iterator mainIt2;
	list<int>::iterator restIt;

	list<NuclPair*> tempList;
	int best = 10000;

	int dist;
	int i, j;
	mainIt2 = mainIt1 = main.begin();
	++mainIt2;
	for (i = 0; i < (int)main.size() - 1; ++i)
	{
		restIt = rest.begin();
		for (j = 0; j < (int)rest.size() - 1; ++j)
		{
			dist = graph[*mainIt1][*restIt] + graph[*restIt][*mainIt2];
			if (dist < best)
			{
				best = dist;

				fflush(0);
				tempList.clear();
				tempList.push_front(new NuclPair(j, i));

			}
			else
				if (dist == best)
				{

					tempList.push_front(new NuclPair(j, i));

				}
			++restIt;

			best = dist;

		}
		++mainIt2;
		++mainIt1;
	}
	int pos = rand() % tempList.size();

	fflush(0);
	while (pos--)
		tempList.pop_front();

	/* rest pos */
	pos = tempList.front()->el;
	restIt = rest.begin();
	while (pos--)
		++restIt;

	/* main pos */
	pos = tempList.front()->pos;
	mainIt1 = main.begin();
	while (pos--)
		++mainIt1;

	main.insert(++mainIt1, *restIt);
	curPath += (best < 10 ? 0 : best - 10);

	rest.erase(restIt);
}

void TSremove(int **graph, list<int>& main, list<int>& tabu, int& curPath)
{

	list<int>::iterator mainIt1;
	list<int>::iterator mainIt2;

	mainIt1 = mainIt2 = main.begin();
	++mainIt2;

	list<int> worstList;

	int worst = 0;
	int dist = 0;
	for (int i = 0; i < (int)main.size() - 1; ++i)
	{
		dist = graph[*mainIt1][*mainIt2];
		if (dist > worst)
		{
			worst = dist;
			worstList.clear();
			worstList.push_back(i);
		}
		else
			if (dist == worst)
				worstList.push_back(i);

		++mainIt1;
		++mainIt2;
	}

	int pos = rand() % worstList.size();

	list<int>::iterator rmvIt = main.begin();
	while (pos--)
		++rmvIt;

	tabu.push_back(*rmvIt);
	main.erase(rmvIt);

}

/*
int TS(int **distGraph, NuclSeq& baseSeq, int tabuListLen, int maxIter,
		int curPath, int maxPath)
{

	list<int> main;
	list<int> rest;
	list<int> tabu;

	vector<int>::iterator it;
	int i;
	for (i = 0; i < baseSeq.seq.size(); ++i)
		if (i < baseSeq.end)
			main.push_back(baseSeq.seq[i]);
		else
			rest.push_back(baseSeq.seq[i]);

	printf("%d = %d + %d\n", baseSeq.seq.size(), main.size(), rest.size());

	TSinsert(distGraph, main, rest, curPath);

	printf("%d = %d + %d\n", baseSeq.seq.size(), main.size(), rest.size());
	printf("path %d \n", curPath);

	main.clear();
	rest.clear();

	return 0;

}
*/
void SA(int **distGraph, NuclSeq& baseSeq, double baseTemp, double maxIter,
		int nuclCount, int maxPath)
{

	double energy = evalEnergy(baseSeq, distGraph, maxPath);
	double curEnergy, dEnergy;

	NuclSeq tempSeq;
	tempSeq.clear();
	double rnd = 0.0;
	double curTemp = baseTemp;
	int curIter = 1;

	printf("start\n");
	while (curIter < maxIter)
	{

		generateNeighbour(baseSeq, distGraph, tempSeq);

		curEnergy = evalEnergy(tempSeq, distGraph, maxPath);
		dEnergy = energy - curEnergy;
		rnd = ((double) (rand() % 10000)) / 10000.0;
		if (exp(-1.0 * (dEnergy / curTemp)) > rnd)
		{
			energy = curEnergy;
			baseSeq.clear();

			baseSeq.seq.insert(baseSeq.seq.begin(), tempSeq.seq.begin(), tempSeq.seq.end());
			baseSeq.end = tempSeq.end;
		}//if
		curTemp = baseTemp / (1.0 + log((double) ++curIter));

		if (curIter == maxIter)
			return;
	}//while
	printf("out\n");
	return;
}//SA


/* params: filename expected_size */
int main(int argc, char **argv)
{

	vector<char*> v;
	NuclSeq base;
	int **graph;
	int i;
	int maxPath = atoi(argv[2]) + 9;
	int maxNucl = atoi(argv[2]);


	loadData(argv[1], 20, v);
	srand(0);
	int n = v.size();
	maxNucl = maxNucl<n ? maxNucl : n;


	graph = new int*[n];
	for (i = 0; i < n; i++)
		graph[i] = new int[n];

	createGraph(v, graph);
	srand(time(0));
	//// ALGO //// greedyTSP(graph, base, rand()%n, n, maxPath);
	std::vector<std::string> in_gr;
	FOREACH(i,v)
	{
		in_gr.push_back(*i);
	}

	int reps = 0;
	double t;
	int best_a = 0;
	reps = 0;
	t = clock();
	for (int j=0;j<MAX_ITERS && best_a<(int)in_gr.size();j++)
	{
		int a = mgreedy(in_gr, graph, maxPath, best_a);
		if (a>best_a) best_a=a;
		reps++;
	}
	t = clock() - t;
	printf("T ; %4d ; %4d ; %.2f ; %7.4f ; %3d\n", best_a, maxNucl, (double) best_a / (double) maxNucl, (double)t/(double)CLOCKS_PER_SEC, reps );
	displayBestSeq(graph);
	clearBest();


/*	int best=0;
	reps = 0;
	t = clock();
	for (int j=0;j<MAX_ITERS && best < in_gr.size();j++){
	  	base.clear();
		greedyTSP(graph, base, rand()%n, n, maxPath);
	  	if(best < base.end)
			best = base.end;
	  	reps++;
	}
	t = clock() - t;
	printf("K ; %4d ; %4d ; %.2f ; %7.4f ; %3d\n", best, maxNucl, (double)best/(double)maxNucl, (double)t/(double)CLOCKS_PER_SEC, reps );

	ofstream file;
	file.open("seq.out");
	for (i = 0; i < base.end; ++i)
		file << v[base.seq[i]] << endl;
	file.close();
*/
	cleanUp(v, graph);

	return 0;


}











